package com.ctrip.demo.leetcode;

/**
 * @author xs.wu
 */
public class LeetCode300 {

    public static void main(String[] args) {
        // [10,9,2,5,3,7,101,18]
        lengthOfLIS(new int[]{10,9,2,5,3,7,101,18});
    }


    public static int lengthOfLIS(int[] nums) {

        int len = nums.length;

        int[] dp = new int[len];

        int max = 1;

        for(int i = 0; i < len; i ++) {
            dp[i] = 1;
            for(int j = 0; j < i; j ++) {
                if(nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            max =  Math.max(dp[i], max);
        }
        return max;
    }
}
